package 面试题41_数据流中的中位数;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 10:52 2021/3/15
 * @Description：使用最大堆最小堆实现
 */

// 题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么
// 中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，
// 那么中位数就是所有数值排序之后中间两个数的平均值。
public class MedianFinder {
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小顶堆，默认容量为11
//    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() { //大顶堆，容量11
//        public int compare(Integer i1, Integer i2) {
//            return i2 - i1;
//        }
//    });

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {

    }

    public void addNum(int num) {
        // 为了使数据平均分配到两堆：若两堆数目相等，就让minHeap的元素个数+1
        // 具体做法分两步：1.将新元素加入到maxHeap；2.将maxHeap的堆顶元素加入到minHeap
        if (maxHeap.size() == minHeap.size()) {
            maxHeap.add(num);

            minHeap.add(maxHeap.poll());
        }

        // 不相等的话：1.将新元素加入到minHeap；2.将minHeap的堆顶元素加入到maxHeap
        else {
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        }
    }

    public double findMedian() {
        // 如果元素的个数是偶数
        if (maxHeap.size() == minHeap.size()) {
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        } else {
            return minHeap.peek();
        }
    }
}
